Пентус А.Е. Математическая теория формальных языков. - М.: Изд-во "Интернет-университет информационных технологий - ИНТУИТ.ру", 2006. - 248 c.: ил.
10. Лекция: Автоматы с магазинной памятью
В данной лекции рассматриваются автоматы с магазинной памятью, в которых помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как магазин. Даются необходимые определения, и доказывается, что автоматы с магазинной памятью распознают в точности контекстно-свободные языки. Приведены примеры практического использования автоматов с магазинной памятью и приведены упражнения для самостоятельной проработки
Подобно тому, как праволинейным грамматикам соответствуют конечные автоматы, контекстно-свободным грамматикам соответствуют автоматы с магазинной памятью (МП-автоматы). В таком автомате, помимо ограниченной памяти, хранящей текущее состояние, имеется потенциально бесконечная память, используемая как стек (магазин), то есть структура данных, где в каждый момент доступен только тот элемент, который был добавлен позже остальных присутствующих на данный момент элементов.
Для наглядности стек обычно изображают вертикально, так, что доступный элемент данных (вершина) находится наверху. Но при формальном определении конфигурации (мгновенного состояния) МП-автомата удобно считать все содержимое стека конечной последовательностью символов, то есть словом (в алфавите, в котором перечислены все возможные данные, "умещающиеся" в одной ячейке стека). Прежде чем определить конфигурацию, придется принять произвольное соглашение о том, в каком порядке записывать содержимое стека в этом слове. В этой книге считается, что вершина стека находится в начале слова (то есть слева). В разделе 10.1 даются необходимые определения. В разделе 10.2 доказывается, что МП-автоматы распознают в точности контекстно-свободные языки.
10.1. Определение автомата с магазинной памятью
Определение 10.1.1. Автомат с магазинной памятью (МП-автомат, магазинный автомат, стековый автомат, pushdown automaton) - это шестерка , где , , и - конечные множества, , и
Здесь Q - множество состояний, - входной алфавит, - алфавит магазинной памяти (stack alphabet), - множество переходов (transition relation), элементы I называются начальными состояниями, элементы F - заключительными или допускающими состояниями.
Пример 10.1.2. Пусть Q = {1,2}, , ,
, . Тогда - МП-автомат.
Замечание 10.1.3. МП-автоматы можно изображать в виде диаграмм состояний. На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое допускающее состояние отмечается на диаграмме двойным кружком. Стрелка с пометкой , ведущая из p в q, показывает, что является переходом данного МП-автомата.
Пример 10.1.4. Ниже приведена диаграмма МП-автомата из примера 10.1.2.
Определение 10.1.5. Конфигурацией МП-автомата называется любая тройка , где , , .
Определение 10.1.6. Определим на множестве всех конфигураций МП-автомата бинарное отношение (такт работы) следующим образом. Если , и , то .
Замечание 10.1.7 Обычно из контекста ясно, о каком МП-автомате идет речь. Тогда вместо будем писать .
Пример 10.1.8. Для МП-автомата из примера 10.1.2 выполняется и .
Определение 10.1.9. Бинарное отношение определяется как рефлексивное, транзитивное замыкание отношения .
Пример 10.1.10. Для МП-автомата из примера 10.1.2 выполняется и .
Лемма 10.1.11. Если и , то .
Доказательство. Лемму легко доказать индукцией по количеству тактов в вычислительном процессе, ведущем из конфигурации в конфигурацию .
Определение 10.1.12. Слово допускается МП-автоматом , если найдутся такие состояния и , что .
Определение 10.1.13. Язык, распознаваемый МП-автоматом, - множество всех слов, допускаемых этим МП-автоматом. Язык, распознаваемый МП-автоматом M, обозначается L(M).
Замечание 10.1.14. Обычно в учебниках используется более узкое определение МП-автомата,...
